// https://www.lintcode.com/problem/relative-ranks/

public class Solution {
    /**
     * @param nums: List[int]
     * @return: return List[str]
     */
    public String[] findRelativeRanks(int[] nums) {
        // write your code here
        String[] ret = new String[nums.length];
        int[] sortedNums = nums.clone();
        String[] medals = new String[]{"Gold Medal", "Silver Medal", "Bronze Medal"};
        Arrays.sort(sortedNums);
        reverse(sortedNums);
        HashMap<Integer, String> map = new HashMap<>();
        for (int i = 0; i < sortedNums.length; ++i) {
            if (i < 3) {
                map.put(sortedNums[i], medals[i]);
            }
            else {
                map.put(sortedNums[i], String.valueOf(i + 1));
            }
        }
        for (int i = 0; i < nums.length; ++i) {
            ret[i] = map.get(nums[i]);
        }
        return ret;
    }
    
    protected void reverse(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            ++i;
            --j;
        }
    }
}